#include <deque>
#include <string>
#include <vector>
// 最长有效括号
// 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。


// 我们定义 dp[i]\textit{dp}[i]dp[i] 表示以下标 iii 字符结尾的最长有效括号的长度。我们将 dp\textit{dp}dp 数组全部初始化为 000 。显然有效的子串一定以 ‘)’\text{‘)’}‘)’ 结尾，因此我们可以知道以 ‘(’\text{‘(’}‘(’ 结尾的子串对应的 dp\textit{dp}dp 值必定为 000 ，我们只需要求解 ‘)’\text{‘)’}‘)’ 在 dp\textit{dp}dp 数组中对应位置的值。
//
// 我们从前往后遍历字符串求解 dp\textit{dp}dp 值，我们每两个字符检查一次：
//
//     s[i]=‘)’s[i] = \text{‘)’}s[i]=‘)’ 且 s[i?1]=‘(’s[i - 1] = \text{‘(’}s[i?1]=‘(’，也就是字符串形如 “……()”“……()”“……()”，我们可以推出：
//
// dp[i]=dp[i?2]+2 \textit{dp}[i]=\textit{dp}[i-2]+2 dp[i]=dp[i?2]+2
//
// 我们可以进行这样的转移，是因为结束部分的 "()" 是一个有效子字符串，并且将之前有效子字符串的长度增加了 $2$ 。
//
// 2. s[i]=‘)’s[i] = \text{‘)’}s[i]=‘)’ 且 s[i?1]=‘)’s[i - 1] = \text{‘)’}s[i?1]=‘)’，也就是字符串形如 “……))”“……))”“……))”，我们可以推出： 如果 s[i?dp[i?1]?1]=‘(’s[i - \textit{dp}[i - 1] - 1] = \text{‘(’}s[i?dp[i?1]?1]=‘(’，那么
// dp[i]=dp[i?1]+dp[i?dp[i?1]?2]+2 \textit{dp}[i]=\textit{dp}[i-1]+\textit{dp}[i-\textit{dp}[i-1]-2]+2 dp[i]=dp[i?1]+dp[i?dp[i?1]?2]+2
//
// 我们考虑如果倒数第二个 ‘)’\text{‘)’}‘)’ 是一个有效子字符串的一部分（记作 subssub_ssubs?），对于最后一个 ‘)’\text{‘)’}‘)’ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’\text{‘(’}‘(’ ，且它的位置在倒数第二个 ‘)’\text{‘)’}‘)’ 所在的有效子字符串的前面（也就是 subssub_ssubs? 的前面）。因此，如果子字符串 subssub_ssubs? 的前面恰好是 ‘(’\text{‘(’}‘(’ ，那么我们就用 222 加上 subssub_ssubs? 的长度（dp[i?1]\textit{dp}[i-1]dp[i?1]）去更新 dp[i]\textit{dp}[i]dp[i]。同时，我们也会把有效子串 “(subs)”“(sub_s)”“(subs?)” 之前的有效子串的长度也加上，也就是再加上 dp[i?dp[i?1]?2]\textit{dp}[i-\textit{dp}[i-1]-2]dp[i?dp[i?1]?2]。
//
// 最后的答案即为 dp\textit{dp}dp 数组中的最大值。
//https://leetcode.cn/problems/longest-valid-parentheses/solutions/314683/zui-chang-you-xiao-gua-hao-by-leetcode-solution/

class Solution
{
public:
    static void Demo()
    {
        std::string s("()(())");
        Solution Instance;
        int Value = Instance.longestValidParentheses(s);
    }

    int longestValidParentheses(std::string s)
    {
        if (!s.size())
        {
            return 0;
        }
        std::vector<int> dp(s.size(), 0);
        int Index = 0;
        for (auto& Char : s)
        {
            if (Char == ')')
            {
                if (Index - 1 >= 0)
                {
                    if (s[Index - 1] == '(')
                    {
                        if (Index - 2 >= 0)
                        {
                            dp[Index] = dp[Index - 2] + 2;
                            ++Index;
                            continue;
                        }
                        else
                        {
                            dp[Index] = 2;
                            ++Index;
                            continue;
                        }
                    }
                    else //s[Index-1]==')'
                    {
                        if (Index - 2 >= 0)
                        {
                            if (Index - dp[Index - 1] - 1 >= 0)
                            {
                                if (s[Index - dp[Index - 1] - 1] == '(')
                                {
                                    dp[Index] = dp[Index - 1] + 2;
                                    if(Index - dp[Index - 1] - 1-1>=0)
                                    {
                                        dp[Index]+=dp[Index - dp[Index - 1] - 1-1];
                                    }
                                    ++Index;
                                    continue;
                                }
                                else
                                {
                                    ++Index;
                                    continue;
                                }
                            }
                            else
                            {
                                ++Index;
                                continue;
                            }
                        }
                        else
                        {
                            ++Index;
                            continue;
                        }
                    }
                }
                else
                {
                    ++Index;
                    continue;
                }
            }
            ++Index;
        }
        int Max = dp[0];
        for (auto& Num : dp)
        {
            Max = std::max(Max, Num);
        }
        return Max;
    }

    int longestValidParenthesesWrong(std::string s)
    {
        std::deque<char> Stack;
        int MaxValid = 0;
        int Counter = 0;
        for (auto& Char : s)
        {
            if (Char == '(')
            {
                Stack.push_back(Char);
            }
            else if (Char == ')')
            {
                if (Stack.size())
                {
                    if (Stack.back() == '(')
                    {
                        Stack.pop_back();
                        ++Counter;
                    }
                }
                else
                {
                    if (Counter > MaxValid)
                    {
                        MaxValid = Counter;
                        Counter = 0;
                        Stack.clear();
                    }
                }
            }
        }
        int Minus = 0;
        while (Stack.size())
        {
            if (Stack.back() == '(')
            {
            }
        }
        if (Counter > MaxValid)
        {
            MaxValid = Counter;
        }
        return MaxValid * 2;
    }
};
